/**
 * @program: 力扣刷题
 * @description
 * @author: LiChong
 * @create: 2021-06-11 23:54
 **/
public class Code04 {
    public static void main(String[] args) {
        int[] A = {0,0,0,0,0};
        int[] B ={-1,0,0,0,0,0,1};
        System.out.println(findMedianSortedArrays2(A, B));
    }

    /**
     * 解法一：双指针法，依次从小到大遍历数组，时间复杂度O(m+n);
     * @param nums1
     * @param nums2
     * @return
     */
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len = nums1.length+nums2.length;
        int last=0,cur = 0;
        int nums1Point = 0,nums2point=0;
        for (int i = 0; i <=len/2 ; i++) {
            last = cur;
            if (nums1Point<nums1.length&&(nums2point>=nums2.length||nums1[nums1Point]<=nums2[nums2point])){
                cur = nums1[nums1Point];
                nums1Point++;
            }else {
                cur = nums2[nums2point];
                nums2point++;
            }
        }
        if (len%2==0){
            return (double) (last+cur)/2;
        }else {
            return cur;
        }


    }
    /**
     * 解法二：每次排除一个数组k/2的数字，利用的是二分法的思想。
     * @param nums1
     * @param nums2
     * @return
     */
    public static double findMedianSortedArrays2(int[] nums1, int[] nums2){
        int length = nums1.length+nums2.length;
        int k = length/2;
        if (length%2==0){
            return (double) (getKNum(nums1,nums2,k+1)+getKNum(nums1,nums2,k))/2;
        }else {
            return getKNum(nums1,nums2,k+1);
        }
    }
    private static double getKNum(int[] nums1, int[] nums2, int k) {
        int nums1Len = nums1.length;
        int nums2Len = nums2.length;
        int half = k/2;
        int newIndex1 = 0,newIndex2 = 0;
        int pivotIndex1 = 0,pivotIndex2 = 0;
        while(true){
            if (newIndex1==nums1Len){
                return nums2[newIndex2+k-1];
            }
            if (newIndex2==nums2Len){
                return nums1[newIndex1+k-1];
            }
            if (k==1){
                return Math.min(nums1[newIndex1],nums2[newIndex2]);
            }
            pivotIndex1 = Math.min(newIndex1+half,nums1Len)-1;
            pivotIndex2 = Math.min(newIndex2+half,nums2Len)-1;
            if (nums1[pivotIndex1]<=nums2[pivotIndex2]){
                k = k -(pivotIndex1-newIndex1+1);
                newIndex1 = pivotIndex1+1;
            }else {
                k = k -(pivotIndex2-newIndex2+1);
                newIndex2 = pivotIndex2+1;
            }
            half = k/2;
        }
    }


}
